package com.example.demo.suanfa_2tree;

/**
 * 找到一个节点的后继
 *
 * 中序遍历形成的数组  x节点 的下个节点，就是后继
 * 方法1：通过x节点，找到head
 *      通过head 中序遍历，找到x节点后继
 *      此时间复杂度 为 O(N)
 * 方法2：能否有，O(k) k 为x到后继的 在二叉树上的最短距离
 */
public class SuccessorNodeDemo {

    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node getSuccessorNode(Node node) {
        if (node== null ){
            return null;
        }
        if (node.right != null) {
            // 错误，因该找右树上的最左！！！！
            return node.right;
        }

        Node p = node.parent;
//        while (p != null && p.left != p){
        // 此段代码，可能不能成功！！！需要改写
        while (p != null && p.right == node){
            node = p;
            p = p.parent;
        }
        if (p == null){
            return null;
        }else {
            return p.right;
        }
    }

}
